package SlideWindows;

import java.util.HashMap;

/**
 * 最长 不含重复字符串的子串
 * 这题的DP解法很多种， dp[i][j] = 字符 i 和 j的最长不重复
 */
public class L3_LongestSubstringWithoutRepet {
    /**
     * 滑动窗口， 然后，碰到有重复的字符串，那个Math.max 很重要，因为会有以前记录，但是，不在窗口内的
     * put进去的时候，i+1，是因为要从下个字符串算，因为这个记录进去的字符串是 在重复的时候，才会用
     */
    public int lengthOfLongestSubstring(String s) {
        char[] ss = s.toCharArray();
        HashMap<Character, Integer> maps = new HashMap<>();
        int n = ss.length, left=0, right, max=0;
        if(n==0) return 0;

        for(right=0; right<n; right++){
            //不合法，然后，直接挪动做指针到 当前的right位置，因为已经有重复的了
            if(maps.containsKey(ss[right]) ){
                //滑动窗口， 然后，碰到有重复的字符串，那个Math.max 很重要，因为会有以前记录，但是，不在窗口内的
                //为了处理  abbca的情况
                left = Math.max(left, maps.get(ss[right]));
            }
            max = Math.max(max, right - left +1);
            maps.put(ss[right], right + 1);//key值为字符，value值为字符位置+1，加1表示从字符位置后一个才开始不重复
        }
        return max;
    }
    public static void main(String[] args){
        L3_LongestSubstringWithoutRepet l = new L3_LongestSubstringWithoutRepet();
//        l.lengthOfLongestSubstring("dadv");
        l.lengthOfLongestSubstring("abbca");
    }
}
